#pragma once
#include <assert.h>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
namespace my_list
{
	// 双向带头循环链表
	template <typename T>
	struct ListNode
	{
		T data = T();
		ListNode* _next = nullptr;
		ListNode* _pre = nullptr;
	};

	// 如果是const_iterator呢？
	// 得另外定义一个struct const_iterator
	// 要学会复用，使用模板完成const_iterator
	// template<typename T>
	template <typename T, typename Ref, typename Ptr>
	// 模拟指针的行为
	struct list_iterator
	{
		typedef ListNode<T> node;
		typedef list_iterator<T, Ref, Ptr> Self;
		list_iterator()
		{
		}

		list_iterator(node* n)
			: _node(n)
		{
		}

		// T& operator*()
		// {
		// 	return *_node;
		// }
		// // _node->val
		// T* operator->()
		// {
		// 	return _node;
		// }
		// iterator<T>& operator++()
		// {
		// 	return iterator<T>(_node->next);
		// }

		// T&
		//  模拟内置类型指针的行为
		Ref operator*()
		{
			// return *_node;
			return _node->data;
		}

		// T*
		// -> 是为了给T是自定义类型用的  struct AA
		// 结构体的指针，访问变量时使用->
		// 模拟自定义类型指针行为
		Ptr operator->()
		{
			// return _node;
			return &_node->data;
		}

		// ++it
		Self& operator++()
		{
			// return Self(_node->next);
			_node = _node->_next;
			return *this;
		}
		Self& operator++(int)
		{
			// return Self(_node->next);
			Self tmp = *this;
			_node = _node->_next;
			return tmp;
		}

		Self& operator--()
		{
			_node = _node->_pre;
			return *this;
		}

		Self& operator--(int)
		{
			Self tmp = *this;
			_node = _node->_pre;
			return tmp;
		}

		// 只加引用还不行还得加const
		// 防止传入的参数是一个右值
		bool operator==(const Self& t) const
		{
			return _node == t._node;
		}
		bool operator!=(const Self& t) const
		{
			return _node != t._node;
		}

		node* _node;
	};

	template <typename T>
	class list
	{
	public:
		typedef ListNode<T> node;
		// 重命名的类型iterator不能和 struct iterator的名字一样
		// typedef iterator<T,T&,T*> iterator;
		// typedef iterator<T,const T&,const T*> const_iterator;
		typedef list_iterator<T, T&, T*> iterator;
		typedef list_iterator<T, const T&, const T*> const_iterator;

	private:
		node* get_node(T data)
		{
			node* n = new node;
			n->data = data;
			return n;
		}
		node* get_tail()
		{
			return _head->_pre;
		}

	public:
		void init()
		{
			_head = new node;
			_head->_next = _head;
			_head->_pre = _head;
			_head->data = 0;
		}
		bool empty()
		{
			return _head->_next == _head && _head->_pre == _head;
		}

		iterator begin()
		{
			return iterator(_head->_next);
		}
		iterator end()
		{
			return iterator(_head);
		}

		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}

		const_iterator end() const
		{
			return const_iterator(_head);
		}

		list()
		{
			init();
		}

		list(size_t n, const T& data)
		{
			init();
			while (n)
			{
				push_back(data);
				n--;
			}
		}

		template <typename InputIterator>
		list(InputIterator first, InputIterator last)
		{
			init();
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}

		void swap(list<T>& x)
		{
			std::swap(_head, x._head);
		}

		list(const list<T>& x)
		{
			init();
			list<T> tmp(x.begin(), x.end());
			swap(tmp);
		}
		// 0  1 2 3
		iterator insert(iterator pos, const T& x = T())
		{
			node* next = pos._node;
			node* prev = next->_pre;

			node* new_node = get_node(x);
			new_node->_next = next;
			new_node->_pre = prev;

			next->_pre = new_node;
			prev->_next = new_node;

			return pos;
		}

		void push_back(const T& data)
		{
			// node* n = get_node(data);
			// node* tail = get_tail();

			// _head->_pre = n;
			// n->_next = _head;

			// n->_pre = tail;
			// tail->_next = n;

			insert(end(), data);
		}

		void push_front(const T& data)
		{
			// node* n = get_node(data);
			// node* next = _head->_next;

			// next->_pre = n;
			// n->_next = next;

			// n->_pre = _head;
			// _head->_next = n;

			insert(begin(), data);
		}

		iterator erase(iterator pos)
		{
			assert(pos != end());
			node* next = pos._node->_next;
			node* prev = pos._node->_pre;

			prev->_next = next;
			next->_pre = prev;
			delete pos._node;

			return iterator(next);
		}

		void pop_back()
		{
			// assert(!empty());

			// node *tail = get_tail();
			// node *pre = tail->_pre;

			// pre->_next = _head;
			// _head->_pre = pre;

			// delete tail;
			erase(iterator(end()._node->_pre));
		}

		void pop_front()
		{
			// assert(!empty());
			// node *del = _head->_next;
			// node *next = del->_next;

			// _head->_next = next;
			// next->_pre = _head;
			// delete del;
			erase(begin());
		}

		list<T>& operator=(const list<T>& x)
		{
			list<T> tmp(x.begin(), x.end());
			swap(tmp);
			return *this;
		}
		list<T>& operator=(list<T>&& x)
		{
			swap(x);
			return *this;
		}

	private:
		node* _head;
	};

	void list_test1()
	{
		list<int> l;
		l.push_back(1);
		l.push_back(2);
		l.push_back(3);

		l.push_front(3);
		l.push_front(2);
		l.push_front(1);

		l.pop_front();
		l.pop_back();
	}

	void list_test2()
	{
		list<int> l;
		l.push_back(1);
		l.push_back(2);
		l.push_back(3);
		list<int>::iterator it = l.begin();
		while (it != l.end())
		{
			cout << *it << " ";
			it++;
		}
		cout << endl;
		l.push_front(3);
		l.push_front(2);
		l.push_front(1);
		it = l.begin();
		while (it != l.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		l.pop_front();
		it = l.begin();
		while (it != l.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		l.pop_back();
		it = l.begin();
		while (it != l.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}
	void fun(const list<int> l)
	{
		list<int>::const_iterator it = l.begin();
		for (auto e : l)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void list_test3()
	{
		list<int> l;
		l.push_back(1);
		l.push_back(2);
		l.push_back(3);
		fun(l);

		l.push_front(3);
		l.push_front(2);
		l.push_front(1);
		fun(l);

		l.pop_front();
		l.pop_back();
		fun(l);
	}
	struct AA
	{
		int _a;
		int _b;
		AA(int a = 1, int b = 2)
			: _a(a), _b(b)
		{
		}
	};
	void list_test4()
	{
		list<AA> l;
		AA a;
		l.push_back(a);
		list<AA>::iterator it = l.begin();
		it++;
		cout << (*it)._a << " " << (*it)._b << endl;
		cout << it->_a << " " << it->_b << endl;
		cout << it.operator->()->_a << " " << it.operator->()->_b << endl;
	}

	void list_test5()
	{
		list_test2();
	}

	void list_test6()
	{
		std::vector<int> v{ 1, 2, 3, 4 };
		list<int> l(v.begin(), v.end());
		l.push_back(10);
		l.push_front(10);
		for (auto e : l)
		{
			cout << e << " ";
		}
		cout << endl;
		l.pop_front();
		l.pop_back();
		for (auto e : l)
		{
			cout << e << " ";
		}
		cout << endl;

		cout << "------------------" << endl;

		list<int> l2;
		l2 = std::move(l);
		for (auto e : l2)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}